package stackAndQueue

import (
	"container/heap"
	"math"
	"sort"
)

/*
优先队列（堆）

时间复杂度：O(NlogN) 对会议时间进行排序，NlogN，最坏情况下将需要N个会议室，对堆进行N次插入操作，每次插入后将最值元素放入堆顶需要logN
空间复杂度:O(N) 最坏情况下需要插入N个元素到堆中，总共需要N的空间
*/

func minMeetingRooms(intervals [][]int) (res int) {
	// 根据开始时间进行排序
	sort.Slice(intervals, func(i, j int) bool {
		// 使表达式为true的i所对应元素排前面，j排后面；否则i排后，j排前
		// 令会议开始时间更小的排前面，会议开始时间更大的排后面
		return intervals[i][0] < intervals[j][0]
	})

	// 构造最小堆
	h := &Heap{}
	heap.Init(h)

	// 一开始按照会议开始时间从小到大排好序，然后逐个遍历会议时间，如果堆为空则将会议结束时间存入最小堆
	// 每次最小堆的堆顶保留的是会议结束时间最小（也就是最早结束）的会议，如果后面的会议开始时间比最小结束时间晚，则说明堆顶的会议结束后可以把
	// 房间空出来给后面的会议，如果后面会议的开始时间比堆顶的最小结束时间都小，则说明最早结束的会议还没开完后面的会议就得先开始，则需要添加房间
	for _, interval := range intervals {
		if h.Len() < 1 {
			heap.Push(h, interval[1])
		} else {
			if h.arr[0] <= interval[0] {
				heap.Pop(h)
			}
			heap.Push(h, interval[1])
		}
	}
	return h.Len()
}

// 转换为上下车问题
func minMeetingRooms1(intervals [][]int) (res int) {
	meetings := make([][]int, 0)
	// 例如会议时间有：[[0,30],[5,10],[15,20]]
	// 转换为上下车问题，第一个人从0开始上车，30开始下车，第二个人从5开始上车，10开始下车，第三个人从15上车20下车，问车上最多有几个人?
	// 解决方法：将所有的开始和结束时间放到一起进行排序，遇到开始时间，则表示一个人上车，车上总人数+1，遇到一个下车时间，则表示一个人下车，车上人-1
	//  人数 1    2     1     2     1      0
	//      0----5----10----15----20-----30
	// 变化 +1   +1    -1    +1    -1    -1
	//
	// 这里我们将每一个时间（无论开始还是结束）构造成一个包含两个元素的slice，如果是上车时间，则第二个元素为1，表示人数+1
	// 如果是下车时间，则第二个元素为-1，表示人数-1
	for _, interval := range intervals {
		meetings = append(meetings, []int{interval[0], 1}, []int{interval[1], -1})
	}

	// 这里排序需要注意，如果人的上车时间和另一个人的下车时间相同，则应该先将车上的人-1再+1，否则车上最大人数会更大
	sort.Slice(meetings, func(i, j int) bool {
		var order bool
		if meetings[i][0] != meetings[j][0] {
			order = meetings[i][0] < meetings[j][0]
		} else {
			order = meetings[i][1] < meetings[j][1]
		}
		return order
	})

	maxVal := 0
	cnt := 0
	for _, meeting := range meetings {
		cnt += meeting[1]
		maxVal = Max(maxVal, cnt)
	}
	return maxVal
}

func Max(a ...int) int {
	maxVal := math.MinInt32
	if len(a) == 0 {
		return maxVal
	}
	for _, i := range a {
		if maxVal < i {
			maxVal = i
		}
	}
	return maxVal
}

// 有序化
/*
时间复杂度：O(NlogN)
空间复杂度：O(N)
 */
func minMeetingRooms2(intervals [][]int) (res int) {
	startTimings, endTimings := make([]int, len(intervals)), make([]int, len(intervals))
	for i, interval := range intervals {
		startTimings[i] = interval[0]
		endTimings[i] = interval[1]
	}

	// 对开始时间和结束时间分别进行排序
	sort.Ints(startTimings)
	sort.Ints(endTimings)

	start, end := 0, 0
	useRooms := 0
	// 一般遇到大于/小于/等于的情况，在草稿纸上分三种情况进行讨论，然后每种情况列出变量的变化
	// 当开始时间要大于结束时间，则说明有一个会议先结束然后再开始新的会议，也就是一个会议先结束然后腾出空间，之后再增加一个空间
	for start < len(intervals) {
		if startTimings[start] >= endTimings[end] {
			useRooms--
			end++
		}
		start++
		useRooms++
	}
	return useRooms
}